1. Field of the Invention
The present invention pertains to error correction of digital data, and particularly to error correction using the Berlekamp-Massey algorithm.
2. Related Art and Other Considerations
Error correction coding techniques are typically employed for digital data that is transmitted on a channel or stored/retrieved with respect to a storage device (such as, for example, an optical disk drive or magnetic media drive). With error correction coding, the data to be transmitted or stored is processed to obtain additional data symbols (called check symbols or redundancy symbols). The data and check symbols together comprise a codeword. After transmission or retrieval, the codeword is mathematically processed to obtain error syndromes which contain information about locations and values of errors. Certain principles regarding error correction coding are provided in Glover et al., Practical Error Correction Design For Engineers, 2nd Edition, Cirrus Logic (1991).
The Reed-Solomon codes are a class of multiple-error correcting codes. One of the most popular methods of decoding is to generate an error location polynomial "sgr"(x);
generate an error evaluator polynomial xcfx89(x) from the error location polynomial;
perform a root search for the error locator polynomial to detect error locations; and then evaluate the error evaluator polynomial at the error location polynomial root to calculate an error value. Most logic circuits for error detection and correction implement the Berkekamp-Massey algorithm.
Examples of error correction coding, including utilization of Reed-Solomon codes, are provided by the following (all of which are incorporated herein by reference): U.S. Pat. No. 5,446,743; U.S. Pat. No. 5,724,368; U.S. Pat. No. 5,671,237; U.S. Pat. No. 5,629,949; U.S. Pat. No. 5,602,857; U.S. Pat. No. 5,600,662; U.S. Pat. No. 5,592,404; and, U.S. Pat. No. 5,555,516.
U.S. Pat. No. 5,446,743, entitled xe2x80x9cCoefficient Updating Method And Apparatus For Reed-Solomon Decoderxe2x80x9d, incorporated herein by reference in its entirety, discloses a Reed-Solomon decoder which forms coefficients of an error locator polynomial "sgr"(x) in a bank of error locator registers and coefficients of an error evaluator polynomial xcfx89(x) in a bank of intermediate registers (xcfx84registers). The decoder of U.S. Pat. No. 5,446,743 comprises a plurality of xe2x80x9cslicesxe2x80x9d, each slice having one syndrome register, one of the error location registers, one of the intermediate registers, is and a modified syndrome register.
For each codeword input to the decoder of U.S. Pat. No. 5,446,743 there are two iterations: a first iteration for obtaining the coefficients of the error location polynomial and a second iteration for obtaining the coefficients of the error evaluator polynomial. Each error location iteration has two phases: a first phase (phase A) and a second phase (phase B). During phase A of each error locator iteration, a current discrepancy dn is generated and the coefficient values in the intermediate registers (xcfx84 registers) are updated. The current discrepancy dn is generated by a discrepancy determination circuit which adds multiplicative products from the slices. During phase B of each error locator.iteration, the coefficients values in the error location registers ("sgr" registers) are updated. At the end of phase B, the inverse of the discrepancy, i.e., dnxe2x88x921, is outputted from a discrepancy inversion circuit. The inverse of the discrepancy becomes known as the inverse of the prior discrepancy or dnxe2x88x921xe2x88x921 during the next error location iteration, and is used for updating the coefficient values in the intermediate registers. The discrepancy determination circuit does not use a ROM-stored lookup table, but instead serially receives the discrepancy in a second basis representation (e.g., dual or xcex2 basis representation) and produces the inverse thereof in a first basis representation (xcex1 basis representation).
Assuming its codewords to comprise m-bit symbols, the decoder of U.S. Pat. No. 5,446,743 thus takes m clock cycles to accomplish each phase of an iteration. Therefore, when m=8, sixteen clock cycles per iteration are required to determine the coefficients of the error location polynomial and another sixteen clock cycles are required to determine the coefficients of the error evaluator polynomial. Moreover, as noted above, such decoder requires four sets of registers per slice.
What is needed, and an object of the present invention, is an error correction technique which can perform error correction operations even more expeditiously.
Using a Berlekamp-Massey process operating with unique recursion rules, a fast correction subsystem performs, for each codeword having m-bit symbols, a series of error locator iterations, followed by a series of error evaluator iterations, followed by a series of correction iterations to generate, and then use, an error pattern for correcting a codeword. The fast correction subsystem includes three sets of registers and three sets of multipliers distributed over v+1 component slices where v is the maximum number of symbol errors that can be corrected. In accordance with the recursion rules, a first set of registers (xe2x80x9c"sgr" registersxe2x80x9d) ultimately contains quantities including coefficients of an error locator polynomial "sgr"(x) for the codeword. A second set of registers (xe2x80x9cxcfx84 registersxe2x80x9d) are utilized, e.g., to update the "sgr" registers. A third set of registers (xe2x80x9cR registersxe2x80x9d) ultimately contains quantities including coefficients of an error evaluator polynomial xcfx89(x) for the codeword.
For each codeword, each error location iteration is performed in two phases. In the first phase [Phase A], the fast correction subsystem generates a quantity including a current discrepancy dn in an accumulator. Also during Phase A the fast correction subsystem of the present invention updates the contents of the xcfx84 registers according to the following general recursion rule:
xe2x80x83xcfx84(n)(x)=x*(xcfx84(nxe2x88x921)(x)+(xcex1ddnxe2x88x921)xe2x88x921"sgr"(n)(x)CHANGE_L)
for d not equal to zero. For one illustrated example embodiment, the general recursion rule for Phase A takes the following form:                                           τ                          (              n              )                                ⁢                      xe2x80x83                    ⁢                      (            x            )                          =                  xe2x80x83                ⁢                  x          *                      (                                                            τ                                      (                                          n                      -                      1                                        )                                                  ⁢                                  xe2x80x83                                ⁢                                  (                  x                  )                                            +                                                α                                      -                    3                                                  ⁢                                  xe2x80x83                                ⁢                                  (                                                            (                                                                                                    (                                                                                          α                                                                  -                                  4                                                                                            ⁢                                                              xe2x80x83                                                            ⁢                                                              (                                                                                                      α                                                                          -                                      3                                                                                                        ⁢                                                                      xe2x80x83                                                                    ⁢                                                                      d                                                                          n                                      -                                      1                                                                                                                                      )                                                                                      )                                                                                -                            1                                                                          ⁢                                                  xe2x80x83                                                ⁢                        CHANGE_L                                            )                                        ⁢                                          xe2x80x83                                        ⁢                                          σ                                              (                        n                        )                                                              ⁢                                          xe2x80x83                                        ⁢                                          (                      x                      )                                                        )                                                      )                                                  =                  xe2x80x83                ⁢                  x          *                      (                                                            τ                                      (                                          n                      -                      1                                        )                                                  ⁢                                  xe2x80x83                                ⁢                                  (                  x                  )                                            +                                                                    (                                                                  α                                                  -                          4                                                                    ⁢                                              xe2x80x83                                            ⁢                                              d                                                  n                          -                          1                                                                                      )                                                        -                    1                                                  ⁢                                  xe2x80x83                                ⁢                                  σ                                      (                    n                    )                                                  ⁢                                  xe2x80x83                                ⁢                                  (                  x                  )                                ⁢                                  xe2x80x83                                ⁢                CHANGE_L                ⁢                                  xe2x80x83                                ⁢                                  (                                      d                    =                                          -                      4                                                        )                                                                        
In the second phase [Phase B] of an error locator iteration, the fast correction subsystem obtains a quantity including the inverse of the current discrepancy. The quantity including the inverse of the current discrepancy is used in Phase A of a next iteration as a quantity including the inverse of the prior discrepancy. Also, in Phase B of an error locator iteration, the fast correction subsystem updates the contents of the "sgr" registers according the following general recursion rule:
"sgr"(n+1)(x)=xcex1d("sgr"(n)xe2x88x92dnxcfx84(n))=xcex1d"sgr"(n)(x)xe2x88x92xcex1ddnxcfx84(n)(x)
for d not equal to zero (d being the same as for the xcfx84 recursion rule). For the illustrated example embodiment, the general recursion rule for Phase B takes the following form:                                           σ                          (                              n                +                1                            )                                ⁢                      xe2x80x83                    ⁢                      (            x            )                          =                  xe2x80x83                ⁢                              (                                          α                                  -                  4                                            ⁢                              xe2x80x83                            ⁢                              σ                                  (                  n                  )                                            ⁢                              xe2x80x83                            ⁢                              (                x                )                                      )                    -                                    (                                                α                                      -                    3                                                  ⁢                                  xe2x80x83                                ⁢                                  d                  n                                            )                        ⁢                          xe2x80x83                        ⁢                          (                                                τ                                      (                    n                    )                                                  ⁢                                  xe2x80x83                                ⁢                                  (                  x                  )                                            )                        ⁢                          xe2x80x83                        ⁢                          α                              -                1                                                                            =                  xe2x80x83                ⁢                              (                                          α                                  -                  4                                            ⁢                              xe2x80x83                            ⁢                              σ                                  (                  n                  )                                            ⁢                              xe2x80x83                            ⁢                              (                x                )                                      )                    -                      (                                          α                                  -                  3                                            ⁢                              xe2x80x83                            ⁢                              (                                                      (                                                                  α                                                  -                          3                                                                    ⁢                                              d                        n                                                              )                                    ⁢                                      xe2x80x83                                    ⁢                                      α                    2                                                  )                            ⁢                              xe2x80x83                            ⁢                              (                                                      τ                                          (                      n                      )                                                        ⁢                                      xe2x80x83                                    ⁢                                      (                    x                    )                                                  )                                                                            =                  xe2x80x83                ⁢                                            α                              -                4                                      ⁢                          xe2x80x83                        ⁢                          σ                              (                n                )                                      ⁢                          xe2x80x83                        ⁢                          (              x              )                                -                                    α                              -                4                                      ⁢                          xe2x80x83                        ⁢                          d              n                        ⁢                          xe2x80x83                        ⁢                          τ                              (                n                )                                      ⁢                          xe2x80x83                        ⁢                          (              x              )                        ⁢                          xe2x80x83                        ⁢                          (                                                i                  .                  e                  .                                ,                                  d                  =                                      -                    4                                                              )                                          
The t number of error locator iterations for a codeword are followed by t number error evaluator iterations for the codeword. Each error evaluator iteration also has both a Phase A and a Phase B. In the illustrated example, the error evaluator iterations for a codeword serve, e.g., to put xcex1xe2x88x927xcfx89k(x) in the R registers and to put xcex1xe2x88x923"sgr"(x) in the "sgr" registers. In this regard, during Phase A of an error evaluator iteration, the fast correction subsystem multiplies the contents of a "sgr" register of a last slice (xcex1xe2x88x924k"sgr"20xe2x88x92k) by a constant xcex1xe2x88x924kxe2x88x923 to yield xcex1xe2x88x923"sgr"20xe2x88x92k, and generates xcex1xe2x88x924kxe2x88x923xcfx8919xe2x88x92k in an accumulator. Then, in Phase B of the error evaluation iteration, the value xcex1xe2x88x923"sgr"20xe2x88x92k is shifted into the "sgr" register of the first slice, with previous values of xcex1xe2x88x923"sgr"20xe2x88x92k from previous iterations being serially shifted into a "sgr" register of an adjacent slice. Also during Phase B of the error evaluator iteration, the quantity xcex1xe2x88x927xcfx8919xe2x88x92k is generated and, on the last clock of Phase B, is parallel shifted into the R register of the first slice while R registers of other slices which have received xcex1xe2x88x927xcfx8919xe2x88x92k values parallel shift into to an R register of an adjacent slice.
In the correction operation, an error location is detected when the sum of the "sgr" registers is 0. When an error location is detected, an error pattern ERR is formed, the error pattern ERR being the quotient DVD/DVR. DVD is the sum of the R registers and DVR is the sum of odd numbered "sgr" registers. The error pattern ERR is output from error generator to an adder for use in correcting the codeword.
Advantageously, both Phase A and Phase B of both the error locator iterations and the error evaluator iterations each require only m/2 clocks. The expeditious operation of fast correction subsystem is facilitated by, among other things, specialized multiplication operations and feedback values used to implement, e.g., the unique recursion rules. The xcex1d term in the recursion rules provides flexibility in circuit implementation; e.g., allowing feedback multiplication for the "sgr" registers rather than syndrome registers (R). In the illustrated embodiment, in the xcex1d term d preferably has the value of xe2x88x924.
Several specialized multipliers are employed by the present invention. A first multiplier is used in Phase A of the error locator iteration to generate, in each slice, a contribution to the current discrepancy quantity (the current discrepancy quantity being, in an illustrated embodiment, xcex1xe2x88x923dn). The first multiplier of a slice comprises two inner product circuits, each of which receive a syndrome value from the R register of the slice as a first input and an eight bit value in the "sgr" registers of the slice as a second input. On each of m/2 clocks of Phase A the "sgr" register is clocked with xcex1xe2x88x921 feedback. The contents of the "sgr" register is output as a second input to a first of the two inner product circuits; an xcex14 multiple of the contents of the "sgr" register is output as a second input to a second of the two inner product circuits. On each clock of Phase A of an error locator iteration both inner product circuits of the first multiplier output a bit of the contribution to the current discrepancy quantity xcex1xe2x88x923dn, the highest order bit being output on the first clock, the second highest order bit being output on the second clock, and so forth. The first inner product circuit of the first multiplier thus outputs four bits of the lower order nibble of the contribution to the current discrepancy quantity xcex1xe2x88x923dn (highest order bit leading in the first clock); the second inner product circuit of the first multiplier thus outputs four bits of the higher order nibble of the contribution to the current discrepancy quantity xcex1xe2x88x923dn (highest order bit leading in the first clock).
The first multiplier is also employed, during Phase B of an error evaluator iteration, to generate, in each slice, a contribution to a quantity xcex1xe2x88x924xe2x88x923xcfx8919xe2x88x92k in the accumulator. In this operation, the first multiplier multiplies the contents of the "sgr" registers (clocked with an xcex1xe2x88x921 feedback multiplier) by the syndromes in accordance with the error evaluator polynomial.
A second multiplier is employed, e.g., during Phase B of an error locator iteration, to update the "sgr" registers according to the unique recursion rule. The second multiplier also comprises two inner product circuits. Both of the inner product circuits of the second multiplier of a slice have contents of the xcfx84 register of that slice as a first input. A second input to the first inner product circuit of the second multiplier is an accumulator value; a second input to the second inner product circuit of the second multiplier is an xcex14 multiple of the accumulator value.
A third multiplier is employed, during Phase A of an error locator iteration, to update the xcfx84 registers according to the unique recursion rule. The third multiplier comprises two sets of eight AND gates (each set being represented by only one AND gate symbol in FIG. 3A). In a first set of eight AND gates comprising the third multiplier of a slice, each AND gates of the set receives a respective one of the eight bit contents of the "sgr" register of the slice (in parallel) as its first input and, as its second input, four lower order bits (in serial, highest order bit leading) of the quantity including the inverse of the prior discrepancy. In a second set of eight AND gates, each AND gates of the set receives an xcex14 multiple of a respective one of the eight bit contents of the "sgr" register of the slice (in parallel) as its first input and, as its second input, four higher order bits (in serial, highest order bit leading) of the quantity including the inverse of the prior discrepancy. With each clock of Phase A, the third multiplier thus receives two bits of the quantity including the inverse of the prior discrepancy, i.e., both a higher order nibble bit and a lower order nibble bit. The bits of the two nibbles comprising the quantity including the inverse of the prior discrepancy are applied in alpha basis representation, the most significant bit of each nibble leading on the first clock. During the second and subsequent clocks of the four clocks of Phase A of the error locator iteration, the contents of the "sgr" registers are multiplied by an xcex1xe2x88x921 feedback multiplier. Thus, the "sgr" registers contain "sgr"(x)xcex1xe2x88x924.
The fast error correction subsystem of the present invention also includes an inverse generator. The inverse generator serves several functions, including the function of generating a quantity including an inverse of the current discrepancy during Phase B of an error locator iteration (i.e., xcex17dnxe2x88x921xe2x88x921), which becomes the quantity including an inverse of the prior discrepancy [xcex17dnxe2x88x921xe2x88x921] during Phase A of the next error locator iteration). In so doing, the quantity including the current discrepancy is applied from the accumulator where it is generated to both of two inversion look up tables. Prior to being applied to a first of the inversion look up tables, the quantity including the current discrepancy is multiplied by xcex1xe2x88x924. Prior to being applied to a second of the inversion look up tables, the quantity including the current discrepancy is multiplied by xcex1xe2x88x928. Each inverse look up table serially outputs, in four successive clocks of Phase B, four bits of the quantity including the inverse of the prior discrepancy, i.e., (xcex17dnxe2x88x921xe2x88x921). In the four successive clocks of Phase B, the first inversion look up table outputs the lower order nibble of the quantity including the inverse of the prior discrepancy, in xcex2 representation, least significant bit leading. Similarly, in the four successive clocks of Phase B, the first inversion look up table outputs the higher order nibble of the quantity including the inverse of the prior discrepancy, in xcex2 representation, least significant bit leading.
The inverse generator performs both a basis representation transformation and a bit order transformation for the quantity including the inverse of the prior discrepancy.
In this regard, the inverse generator serially outputs the quantity including the inverse of the prior discrepancy, i.e., (xcex17dnxe2x88x921xe2x88x921), in xcex1 basis representation, two bits at a time in each of four clocks of Phase B, with most significant bits of each nibble leading in the first clock. The basis representation transformation and a bit order transformation for the quantity including the inverse of the prior discrepancy are accomplished by performing the following (over the four clocks of Phase B of the error locator iteration): (1) applying the output of the first inverse look up table to a first serial shift register; (2) summing the bits of the first two entered bit positions of the first serial shift register; (3) summing the output of (a) the first inverse look up table; the (b) second inverse look up table; and (c) the sum of (2). Thus, the output of the inverse generator becomes, during Phase A of the next error locator iteration, the quantity including the inverse of the prior discrepancy in a form usable by the third multiplier (xcex1 basis representation, two bits at a time in each of four clocks of Phase B, with most significant bits of each nibble leading in the first clock), e.g., for updating the xcfx84 registers.
In the illustrated example embodiment, the quantity xcex14kxe2x88x923xcfx8919xe2x88x92k in the accumulator generated during Phase A of the error evaluator iteration must be multiplied by xcex14kxe2x88x924 prior to being shifted into the R registers for use as error evaluator coefficients. The xcex14kxe2x88x924 multiplication is accomplished using a fourth multiplier which performs an inner product of (1) an xcex1xe2x88x921 multiple of the contents of the accumulator, and (2) the constant xcex14k. The actual result is a times the product of the operands, i.e., xcex1xe2x88x924fxe2x88x923xcfx8919xe2x88x92kxc2x7xcex1xe2x88x921xc2x7xcex14kxc2x7xcex1xe2x88x923=xcex1xe2x88x927xcfx8919xe2x88x92k. The output of the fourth multiplier is two streams of serial bits, i.e., a most significant nibble bit stream and a least significant nibble bit stream, both bit streams being four bits in length, in xcex2 basis representation, and with most significant bit is leading. The output of the higher order nibble of the fourth multiplier is applied to the first serial shift register of the inverse generator; the output of the lower order nibble of the fourth multiplier is applied to the second serial shift register of the inverse generator. The contents of the two serial shift registers of the inverse generator are loaded in parallel into the R register of the first slice as the quantity xcex1xe2x88x927xcfx8919xe2x88x92k on the last clock of Phase B of the error evaluator iteration, and are in xcex2 basis representation. Simultaneously, any R register of other slices which have received xcex1xe2x88x927xcfx8919xe2x88x92k quantities are shifted into the R registers of the next slice.
In the correction operation, the error pattern ERR is generated by multiplication of an inverse of a divisor DVR by a dividend DVD. The dividend DVD is obtained from a sum of terms which include coefficients of an error evaluator polynomial; the divisor DVR is a sum of selected (e.g., odd numbered) terms including coefficients of the error locator polynomial "sgr". The error pattern ERR can then be used to correct the codeword.
The fourth multiplier and the inverse generator are also employed during the correction operation. In the correction operation, the sum of all the odd number "sgr" registers resides in the accumulator (all eight bits) and represents a divisor DVR to be used in the correction procedure. The DVR value in the accumulator is applied to each of the inverse look up tables of the inverse generator for each of four clocks. At each of the four clocks the inverse look up tables both output a bit of the inverse of DVR (in xcex2 basis representation). In like manner with outputting the quantity including the inverse of the prior discrepancy, the inverse generator performs a basis transformation and bit order transformation for the inverse of DVR, outputting the inverse of DVR in two serial streams in four socks in xcex1 basis representation with most significant bit leading for each of the two nibble streams. The bit-outputted inverse of DVR is multiplied by the dividend DVD (the sum of the R registers) to generate the error pattern ERR. Thus, the inverse generator serves both to form the quantity including the inverse of the prior discrepancy during Phase B of the error locator iteration, as well as to determine an inverse of the DVR for correction, and in both instances provides a basis transformation and a bit order transformation for serial streams outputted therefrom.